#include <cstdlib>
#include <iostream>

template <typename DTYPE>
class Node
{
private:
    DTYPE data;
    Node* next;
    Node* prev;
public:
    Node();
    Node(DTYPE _val);
    ~Node(){};
    DTYPE get_data() const;
    void set_data(DTYPE _val);
    Node* get_next() const;
    Node* get_prev() const;
    void set_next(Node* _add);
    void set_prev(Node* _add);
};

template <typename DTYPE>
class LinkedList
{
private:
    Node<DTYPE>* head;
    Node<DTYPE>* tail;
public:
    LinkedList();
    ~LinkedList();
    void append(const Node<DTYPE>& _node);
    void append(DTYPE _val);
    void list() const;
    Node<DTYPE>* find(DTYPE _val) const;
    void delnext (Node<DTYPE>* _add);
    void insert (DTYPE _val);
    DTYPE pop_front();
};


//Node
template<typename DTYPE>
Node<DTYPE>::Node()
{
    next = NULL;
    prev = NULL;
};

template<typename DTYPE>
Node<DTYPE>::Node(DTYPE _val)
{
    data = _val;
    next = NULL;
    prev = NULL;
};

template<typename DTYPE>
DTYPE Node<DTYPE>::get_data() const
{
    return data;
};

template<typename DTYPE>
void Node<DTYPE>::set_data(DTYPE _val)
{
    data = _val;
};

template<typename DTYPE>
Node<DTYPE>* Node<DTYPE>::get_next() const
{
    return next;
};

template<typename DTYPE>
Node<DTYPE>* Node<DTYPE>::get_prev() const
{
    return prev;
};

template<typename DTYPE>
void Node<DTYPE>::set_next(Node<DTYPE>* _add)
{
    next = _add;
};

template<typename DTYPE>
void Node<DTYPE>::set_prev(Node<DTYPE>* _add)
{
    prev = _add;
};


//LinkedList

template <typename DTYPE>
LinkedList<DTYPE>::LinkedList()
{
    head = NULL;
    tail = NULL;
};

template <typename DTYPE>
LinkedList<DTYPE>::~LinkedList()
{
    if (head != NULL)
    {
	Node<DTYPE>* p = head;
	while (p->get_next() != NULL)
	{
	    Node<DTYPE>* t = p;
	    p = p->get_next();
	    delete t;
	}
	delete p;
    }
};

template <typename DTYPE>
void LinkedList<DTYPE>::append(const Node<DTYPE>& _node)
{
    Node<DTYPE>* p = new Node<DTYPE>;
    p->set_data(_node.get_data());
    p->set_prev(tail);
    if (head == tail)
        if(head==NULL)
        head = p;
        else
        head->set_next(p);
    else
        tail->set_next(p);
    tail=p;
};

template <typename DTYPE>
void LinkedList<DTYPE>::append(DTYPE _val)
{
    Node<DTYPE>* p = new Node<DTYPE>;
    p->set_data(_val);
    p->set_prev(tail);
    if (head == tail)
        if(head==NULL)
        head = p;
        else
        head->set_next(p);
    else
        tail->set_next(p);
    tail=p;
};

template <typename DTYPE>
void LinkedList<DTYPE>::list() const
{
    Node<DTYPE>* p = head;
    while (p != tail)
    {
	std::cout << p->get_data() << ", ";
    p=p->get_next();
    }
    std::cout << tail->get_data() <<std::endl;
};

template <typename DTYPE>
Node<DTYPE>* LinkedList<DTYPE>::find(DTYPE _val) const{
    Node<DTYPE>* p = head;
    while(p != tail)
    {
    if(p->get_data()==_val)
        return p->get_prev();
    else
        p=p->get_next();
    }
    //三种情况：head==tail!=NULL; head==tail==NULL; head!=tail and _val does not exist.
    if(p != NULL)//第一种或第三种
    if(p == tail && tail->get_data()==_val)//第一种
    return NULL;
    //第二、三种情况均可描述为无法找到
    std::cout<<"Error(in the function 'find'): can not find it."<<std::endl;
    return NULL;
};

template <typename DTYPE>
void LinkedList<DTYPE>::delnext(Node<DTYPE>* _add){
    Node<DTYPE>* p = head->get_next();
    while(p!=tail&&p->get_prev()!=_add)
    p=p->get_next();
    //三种情况: p is what we want; p is the last; _add does not exist. 
    //第一种
    if(p->get_prev()==_add)
    {
        p->get_next()->set_prev(_add);
        _add->set_next(p->get_next());
        delete p;
    }
    else
        //第二种
        if(p==_add)
        std::cout<<"Error(in the function 'delnext'): it is the last one."<<std::endl;
        //第三种
        else
        std::cout<<"Error(in the function 'delnext'): can not find it."<<std::endl;     
};

template <typename DTYPE>
void LinkedList<DTYPE>::insert (DTYPE _val){
    if(head==NULL)
    append(_val);
    else
    {
        Node<DTYPE>* p = new Node<DTYPE>;
        p->set_data(_val);
        Node<DTYPE>* q = tail;
        while(q != NULL && q->get_data()>_val)
            q=q->get_prev();
        if(head->get_data()>_val)//q is head->prev.
        {
            p->set_next(head);
            head->set_prev(p);
            head=p;
        }
        else
        {
            p->set_next(q->get_next());
            p->set_prev(q);
            if(q!=tail){
            q->get_next()->set_prev(p);
            q->set_next(p);}
            else
            append(*p);
        }
    }
};

template <typename DTYPE>
DTYPE LinkedList<DTYPE>::pop_front()
{
    if (head == NULL)
    {
	std::cout << "Error(in the function 'pop_front'): the list is empty." << std::endl;
	return -1;
    }
    DTYPE data = head->get_data();
    Node<DTYPE>* p = head;
    head = p->get_next();
    delete p;
    if(head==tail){
    Node<DTYPE>* p = tail;
    tail = p->get_prev();
    delete p;
    }
    return data;
};